\relax 
\citation{DasSarmaNPT10}
\citation{IJ90}
\citation{BBF04}
\citation{CTW93}
\citation{KR04}
\citation{K00}
\citation{ZS06}
\citation{AHLP01}
\citation{C05}
\citation{GMS05}
\citation{LCCLS02}
\citation{BAS04}
\citation{KKD01}
\citation{GMS05}
\citation{LawS03}
\citation{LKRG03}
\citation{DT07}
\citation{Broder89}
\citation{BIZ89}
\citation{BFG+03}
\citation{DSW06}
\citation{AKL+79}
\citation{LawS03}
\citation{GKM03}
\citation{ZSS05}
\citation{BBSB04}
\citation{BBSB04}
\citation{ZS06}
\citation{BBSB04}
\citation{ZS06}
\citation{DasSarmaNPT10}
\citation{DasSarmaNPT10}
\citation{DNP09-podc}
\citation{DasSarmaNPT10}
\citation{DNP09-podc}
\citation{peleg}
\citation{PK09}
\@writefile{toc}{\contentsline {section}{\numberline {I}Introduction}{1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {I-A}}Distributed Network Model}{1}}
\citation{LawS03}
\citation{DT07}
\citation{Broder89}
\citation{Wilson96}
\citation{BIZ89}
\citation{GoyalRV09}
\citation{GKM03}
\citation{DNP09-podc}
\citation{DasSarmaNPT10}
\citation{NanongkaiDP11}
\citation{DNP09-podc}
\citation{DNP09-podc}
\citation{DasSarmaNPT10}
\citation{DNP09-podc}
\citation{NanongkaiDP11}
\citation{DasSarmaNPT10}
\citation{DNP09-podc}
\citation{DasSarmaNPT10}
\citation{DasSarmaMP12}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {I-B}}Related Work and Problem Statement}{2}}
\@writefile{toc}{\contentsline {section}{\numberline {II}Theoretical Analysis of Algorithms}{2}}
\newlabel{sec:algos}{{II}{2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {II-A}}Algorithm descriptions}{2}}
\citation{DasSarmaMP12}
\citation{DasSarmaNPT10}
\citation{DasSarmaNPT10}
\citation{DasSarmaMP12}
\citation{GkantsidisMS04}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {II-B}}Previous Results - Rounds and Messages}{3}}
\newlabel{thm:1-walk}{{II.1}{3}}
\newlabel{thm: message-1-walk}{{II.2}{3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {II-C}}Round Complexity}{3}}
\newlabel{thm:round-multi-walk}{{II.3}{3}}
\newlabel{thm:avg-round}{{II.4}{3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {II-D}}Message Complexity}{3}}
\newlabel{thm:message-complexity1}{{II.5}{3}}
\newlabel{thm:avg-message-complexity}{{II.6}{3}}
\newlabel{thm:combined-avg-complexity}{{II.7}{3}}
\newlabel{cor:avg-complexity}{{II.8}{3}}
\@writefile{toc}{\contentsline {section}{\numberline {III}Concentration Bounds on $\kappa $}{3}}
\newlabel{sec:conc}{{III}{3}}
\newlabel{thm:kappabound}{{III.1}{3}}
\@writefile{toc}{\contentsline {section}{\numberline {IV}Experiments}{3}}
\newlabel{sec:exp}{{IV}{3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {IV-A}}Short walk utilization factor $\kappa $}{4}}
\newlabel{fig:plot1c}{{1(a)}{4}}
\newlabel{sub@fig:plot1c}{{(a)}{4}}
\newlabel{fig:plot2}{{1(b)}{4}}
\newlabel{sub@fig:plot2}{{(b)}{4}}
\newlabel{fig:subfigureExample}{{\unhbox \voidb@x \hbox {IV-A}}{4}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {varying length of the walk $\ell $. $n=10K, \eta = 1, \lambda = \sqrt {\ell }$}}}{4}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {varying number of nodes n. $\ell =n$, $\eta = 1, \lambda = \sqrt {\ell }$}}}{4}}
\newlabel{fig:plot3}{{1(c)}{4}}
\newlabel{sub@fig:plot3}{{(c)}{4}}
\newlabel{fig:plot4}{{1(d)}{4}}
\newlabel{sub@fig:plot4}{{(d)}{4}}
\newlabel{fig:subfigureExample}{{\unhbox \voidb@x \hbox {IV-A}}{4}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {varying number of short walks $\eta $. $n = 10K, \ell =n, \lambda = \sqrt {\ell }$}}}{4}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(d)}{\ignorespaces {varying length of short walk $\lambda $. $n = 10K, \ell =n, \eta = \qopname \relax o{log}n$}}}{4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {IV-B}}Message complexity plots}{4}}
\bibstyle{abbrv}
\bibdata{Distributed-RW}
\bibcite{AHLP01}{1}
\bibcite{AKL+79}{2}
\bibcite{BFG+03}{3}
\bibcite{BIZ89}{4}
\bibcite{BBF04}{5}
\bibcite{BAS04}{6}
\bibcite{Broder89}{7}
\bibcite{BBSB04}{8}
\bibcite{C05}{9}
\bibcite{CTW93}{10}
\bibcite{DasSarmaMP12}{11}
\bibcite{DNP09-podc}{12}
\bibcite{DasSarmaNPT10}{13}
\bibcite{DSW06}{14}
\bibcite{DT07}{15}
\bibcite{GKM03}{16}
\bibcite{GMS05}{17}
\bibcite{GkantsidisMS04}{18}
\bibcite{GoyalRV09}{19}
\bibcite{IJ90}{20}
\bibcite{KR04}{21}
\bibcite{KKD01}{22}
\bibcite{K00}{23}
\bibcite{LawS03}{24}
\bibcite{LKRG03}{25}
\bibcite{LCCLS02}{26}
\bibcite{NanongkaiDP11}{27}
\bibcite{PK09}{28}
\bibcite{peleg}{29}
\bibcite{Wilson96}{30}
\bibcite{ZS06}{31}
\bibcite{ZSS05}{32}
\newlabel{fig:Mplot1}{{1(e)}{5}}
\newlabel{sub@fig:Mplot1}{{(e)}{5}}
\newlabel{fig:Mplot2}{{1(f)}{5}}
\newlabel{sub@fig:Mplot2}{{(f)}{5}}
\newlabel{fig:subfigureExample}{{\unhbox \voidb@x \hbox {IV-B}}{5}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(e)}{\ignorespaces {varying length of the walk $\ell $. $n=10K, \eta = 1, \lambda = \sqrt {\ell }$}}}{5}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(f)}{\ignorespaces {varying number of nodes n. $\ell =n$, $\eta = 1, \lambda = \sqrt {\ell }$}}}{5}}
\newlabel{fig:Mplot3}{{1(g)}{5}}
\newlabel{sub@fig:Mplot3}{{(g)}{5}}
\newlabel{fig:Mplot4}{{1(h)}{5}}
\newlabel{sub@fig:Mplot4}{{(h)}{5}}
\newlabel{fig:subfigureExample}{{\unhbox \voidb@x \hbox {IV-B}}{5}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(g)}{\ignorespaces {varying number of short walks $\eta $. $n = 10K, \ell =n, \lambda = \sqrt {\ell }$}}}{5}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(h)}{\ignorespaces {varying length of short walk $\lambda $. $n = 10K, \ell =n, \eta = \qopname \relax o{log}n$}}}{5}}
\@writefile{toc}{\contentsline {section}{References}{5}}
